package com.zjj.algorithm.learning.leetcode.linkedlist;


/**
 * 148. 排序链表 中档题
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 *
 * @author zjj_admin
 * @date 2022/11/13 15:08
 */
public class SortList {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(5, null);
        ListNode node2 = new ListNode(1, node1);
//        ListNode node3 = new ListNode(2, node2);
//        ListNode node4 = new ListNode(1, node3);
        ListNode node5 = new ListNode(3, node2);
        sortList2(node5);
        System.out.println("node5 = " + node5);

    }


    /**
     * 插入排序
     * 这里的方法时
     * 创建一个新链表，将原始链表的每一个元素放在新链表相应的位置
     *
     * @param head
     * @return
     */
    public static ListNode sortList2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode dummy1 = new ListNode();
        dummy1.next = head;
        //创建新的链表头结点
        ListNode dummy2 = new ListNode();
        ListNode curr = dummy1.next;
        while (curr != null) {
            addNode(curr, dummy2);
            curr = curr.next;
        }
        return dummy2.next;
    }

    private static void addNode(ListNode node, ListNode head) {
        ListNode curr = head.next;
        ListNode pre = head;
        ListNode newNode = new ListNode(node.val);
        while (true) {
            if (head.next == null) {
                head.next = newNode;
                break;
            } else {
                if (curr == null) {
                    //当遍历到最后一个节点时，直接将该节点加载最末尾
                    newNode.next = null;
                    pre.next = new ListNode(node.val);
                    break;
                } else {
                    if (newNode.val < curr.val) {
                        newNode.next = curr;
                        pre.next = newNode;
                        break;
                    }
                }
            }

            curr = curr.next;
            pre = pre.next;
        }
    }

    /**
     * 这里使用选择排序
     * 当数据太多时超出了时间限制
     *
     * @param head
     * @return
     */
    public static ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        //构造一个虚拟的头结点
        ListNode dummy = new ListNode();
        //定义一个正在比较的节点
        ListNode minNode;
        //定义最小节点的前一个节点，用于和当前节点交换
        ListNode currNode;
        dummy.next = head;
        currNode = head;
        int temp;
        while (true) {
            //从最小节点的下一个节点开始找
            minNode = currNode;
            while (currNode != null) {
                if (minNode.val > currNode.val) {
                    //改变节点中的数据值
                    temp = minNode.val;
                    minNode.val = currNode.val;
                    currNode.val = temp;
                }
                //将当前的节点向后移
                currNode = currNode.next;
            }

            if (minNode.next != null) {
                //将最小的节点向后移
                //将当前节点指向最小节点的后一位
                minNode = minNode.next;
                currNode = minNode;
            } else {
                break;
            }
        }
        return dummy.next;
    }

}
